|
A tree walking automaton (TWA) is a type of finite automaton that deals with tree structures rather than strings. The concept was originally proposed in . The following article deals with tree walking automata. For a different notion of tree automaton, closely related to regular tree languages, see branching automaton. ==Definition== All trees are assumed to be binary, with labels from a fixed alphabet Σ. Informally, a tree walking automaton ''A'' (TWA) is a finite state device which walks over the tree in a sequential manner. At each moment ''A'' visits a node ''v'' in state ''q''. Depending on the state ''q'', the label of the node ''v'', and whether the node is the root, a left child, a right child or a leaf, ''A'' changes its state from ''q'' to ''q''‘ and moves to the parent of ''v'' or its left or right child. A TWA accepts a tree if it enters an accepting state, and rejects if its enters a rejecting state or makes an infinite loop. As with string automata, a TWA may be deterministic or nondeterministic. More formally, a (nondeterministic) tree walking automaton over an alphabet Σ is a tuple where ''Q'' is a finite set of states, its subset ''I'', ''F'', and ''R'' is the set of initial, accepting and rejecting states, respectively, and is the transition relation. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「tree walking automaton」の詳細全文を読む スポンサード リンク
|